/* Author: Mark Faust;   
 * Description: This file defines the two required functions for the branch predictor.
 */

/****************************************************************************
  ECE 486 Project 2
  Branch Prediction

  Jinho Park
  Albert Pham
  Antoni Romano
  Hoa Quach

  predictor.cc

  The competition predictor is implemented in the following functions.
The competitino predictor is a hybrid of a perceptron predictor[1] and
a local history predictors. 

The memory budget constraint of the competition is 4Kbyte + 4byte.
This predictor uses 3.878Kbytes of memory.

[1] Dynamic Branch Prediction with Perceptrons Jimenez 2010

    bool PREDICTOR::get_prediction
    void PREDICTOR::update_predictor
****************************************************************************/

#include "predictor.h"
#include <cstdlib>
#include <iostream>


int LocalHistory[ LOCAL_SIZE ] = {0}; //initialize all elemtns to 0
int LocalPrediction[ LOCAL_SIZE ] = {0};
int GlobalChoice[ GLOBAL_SIZE ] = {0};

unsigned int PC = 0;


int Perceptrons[ NUM_PERCEPTRONS ][ NUM_WEIGHTS ] = { 0 };
int BranchHistory[ HISTORY_LENGTH ] = { 0 };


unsigned branch_address = 0;
int index_p = 0;
int perceptron_prediction = 0;
unsigned global_history = 0;
unsigned global_history_p = 0;

using namespace std;

bool PREDICTOR::get_prediction( const branch_record_c* br, const op_state_c* os )
{
	int localH;	// Current local history
	int localP;	// Local prediction
	int GlobalC;	// Current Global Choice

	branch_address = br->instruction_addr;

	PC = br->instruction_addr;
	PC = PC & PC_MASK;		//select 10 bits for use in branch predictor
	PC = PC >> 2;

	GlobalC = GlobalChoice[global_history];

	localH = LocalHistory[PC];		
	localP = LocalPrediction[localH];// local prediction

	// Perceptron
	index_p = getPerceptronIndex();	// get index to the percentron table
	perceptron_prediction = getPrediction(); 	// get prediction result

	if ((GlobalC & GLOBAL_MASK) == LOCAL_CHOSEN)	//if the predictor choice is 1 -> use the local predictor
	{
		if ((localP & LOCAL_MASK) == LOCAL_TAKEN)//evaulate local predictor table entry
			return TAKEN;
		else
			return NOT_TAKEN;
	}
	else				//else use the perceptron predictor
	{
		if( perceptron_prediction >= 0 )	//if the perceptron output is positive, the branch predict is taken 
			return TAKEN;
		else
			return NOT_TAKEN;
	}

}    
 
 
// Update the predictor after a prediction has been made.  This should accept
// the branch record (br) and architectural state (os), as well as a third
// argument (taken) indicating whether or not the branch was taken.
void PREDICTOR::update_predictor( const branch_record_c* br, const op_state_c* os, bool taken )
{
	int LocalH;
	int LocalP;
	int GlobalC;

	bool LP;
	bool GP;

	LocalH = LocalHistory[ PC ];
	LocalP = LocalPrediction[ LocalH ];

	GlobalC = GlobalChoice[ global_history ];

	// Convert the local and perceptron predictions to boolean values.
	if( LocalP & LOCAL_TAKEN )
		GP = TAKEN;
	else
		GP = NOT_TAKEN;

	bool prediction_sign;
	int t;


	if( perceptron_prediction >= 0 )
	{
		LP = TAKEN;
		prediction_sign = true;
	}
	else
	{
		LP = NOT_TAKEN;
		prediction_sign = false;
	}


	if( taken )
	{
		t = 1;
		switch( LocalP )
		{
			case LT_STRONGLY: 				break;	// Predictor bits saturated.

			case LT_LESS_STRONGLY:	LocalPrediction[ LocalH ] = LT_STRONGLY;
									break;

			case LT_LESS_WEAKLY: 	LocalPrediction[ LocalH ] = LT_LESS_STRONGLY;
									break;

			case LT_WEAKLY: 	LocalPrediction[ LocalH ] = LT_LESS_WEAKLY;
									break;

			case LNT_WEAKLY: 	LocalPrediction[ LocalH ] = LT_WEAKLY;
									break;

			case LNT_LESS_WEAKLY: 	LocalPrediction[ LocalH ] = LNT_WEAKLY;
									break;

			case LNT_LESS_STRONGLY: LocalPrediction[ LocalH ] = LNT_LESS_WEAKLY;
									break;

			case LNT_STRONGLY: 	LocalPrediction[ LocalH ] = LNT_LESS_STRONGLY;
									break;

			default: 		cerr << "Predictor Bits out of Range!!!" << endl;
									break;
		}

	}
	else
	{	        
		t = -1;

		switch( LocalP )
		{
			case LT_STRONGLY: 	LocalPrediction[ LocalH ] = LT_LESS_STRONGLY;
									break;

			case LT_LESS_STRONGLY: 	LocalPrediction[ LocalH ] = LT_LESS_WEAKLY;
									break;

			case LT_LESS_WEAKLY: 	LocalPrediction[ LocalH ] = LT_WEAKLY;
									break;

			case LT_WEAKLY: 	LocalPrediction[ LocalH ] = LNT_WEAKLY;
									break;

			case LNT_WEAKLY: 	LocalPrediction[ LocalH ] = LNT_LESS_WEAKLY;
									break;

			case LNT_LESS_WEAKLY: 	LocalPrediction[ LocalH ] = LNT_LESS_STRONGLY;
									break;

			case LNT_LESS_STRONGLY: LocalPrediction[ LocalH ] = LNT_STRONGLY;
									break;

			case LNT_STRONGLY: 				break;	// Predictor bits saturated.

			default: 		cerr << "Predictor Bits out of Range!!!" << endl;
									break;
		}

	}

	// If the local and global predictions are different, then train the global choice
	// to prefer the correct prediction.  If the local and global predictions are the
	// same, no learning is done.
	if( GP != LP )
	{
		if( GP == taken )
		{
			switch( GlobalC )
			{
				case GT_STRONGLY:	break;	// Predictor bits saturated.
	
				case GT_WEAKLY:		GlobalChoice[ global_history ] = GT_STRONGLY;
									break;

				case GNT_WEAKLY: 	GlobalChoice[ global_history ] = GT_WEAKLY;
									break;
	
				case GNT_STRONGLY: 	GlobalChoice[ global_history ] = GNT_WEAKLY;
									break;
	
				default: 		cerr << "Predictor Bits out of Range!!!" << endl;
									break;
			}
		}
		else // LP == taken
		{
			switch( GlobalC )
			{
				case GT_STRONGLY: 	GlobalChoice[ global_history ] = GT_WEAKLY;
									break;	
	
				case GT_WEAKLY: 	GlobalChoice[ global_history ] = GNT_WEAKLY;
									break;
	
				case GNT_WEAKLY: 	GlobalChoice[ global_history ] = GNT_STRONGLY;
									break;
	
				case GNT_STRONGLY: 	break;
	
				default: 		cerr << "Predictor Bits out of Range!!!" << endl;
									break;
			}
		}
	}

	// Update the branch history with the actual outcome of the branch.
	if( taken )
	{
		global_history = global_history << 1; 
		global_history = global_history & BRANCH_MASK;
		global_history = global_history | BRANCH_TAKEN;
	}
	else // Branch not taken.
	{
		global_history = global_history << 1; 
		global_history = global_history & BRANCH_MASK;
	}

	// Update the local history with the actual outcome of the branch.
	if( taken )
	{
		LocalHistory[ PC ] = LocalHistory[ PC ] << 1;
		LocalHistory[ PC ] = LocalHistory[ PC ] & LOCAL_HISTORY_MASK;
		LocalHistory[ PC ] = LocalHistory[ PC ] | BRANCH_TAKEN;
	}
	else // Branch not taken.
	{
		LocalHistory[ PC ] = LocalHistory[ PC ] << 1;
		LocalHistory[ PC ] = LocalHistory[ PC ] & LOCAL_HISTORY_MASK;
	}

	    
	if( ( prediction_sign != taken ) ||  ( abs( perceptron_prediction ) <= PHI ) )
	{
		for( int i = 0; i < NUM_WEIGHTS; ++i )
		Perceptrons[ index_p ][ i ] = Perceptrons[ index_p ][ i ] + ( t * BranchHistory[ i ] );
	}

	for( int i = 0; i < HISTORY_LENGTH - 1; ++i )
	BranchHistory[ i ] = BranchHistory[ i + 1 ];

	BranchHistory[ HISTORY_LENGTH - 1 ] = t;
	
	return;
}

// Get the perceptron line indice by hashing the branch address (mod number of perceptrons)
// and by XORing with the lower global_history bits to take the global history 
// in to the account

int getPerceptronIndex()
{
	int perceptron_index;
	
	perceptron_index = branch_address ^ global_history;
	perceptron_index &= BRANCH_MASK;
	perceptron_index %= NUM_PERCEPTRONS;

	return perceptron_index;
}

// Get the prediction returns n > 0 for taken branches, returns n <= 0 for not-taken branches

int getPrediction()
{
	int prediction_guess = 0;

	for( int i = 1; i < NUM_WEIGHTS; ++i )
		prediction_guess = prediction_guess + ( BranchHistory[ i ] * Perceptrons[ index_p ][ i ] );

	prediction_guess = prediction_guess + Perceptrons[ index_p ][ 0 ];

	return prediction_guess;
}
